#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

 

示例 1：


输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：



输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


//返回翻转的头节点
ListNode * reversreK_r(ListNode * &head)
{
    if (head== nullptr||head->next== nullptr)
        return head;

    ListNode * ret=reversreK_r(head->next);
    //1 2 3 4
    head->next->next=head;
    head->next= nullptr;
    return ret;
}

//TODO 我特么不会写   返回翻转后的头结点
ListNode *reverseKGroup(ListNode *head, int k) {
    ListNode* l=head;
    for (int i = 0; i <k-1 ; ++i) {
        if (head== nullptr)
            return l;//直接返回头节点 因为不足k 不用翻转
        else
        {
            head=head->next;
        }

    }
    //得加上这样一句。。。。
    if(head==nullptr)
        return l;

    // 此时 head 已经指向第k个
    ListNode* nextNode=head->next;

    head->next= nullptr;

    ListNode* revserNode= reversreK_r(l);//翻转后的第一个节点

    l->next=reverseKGroup(nextNode,k);

    return revserNode;

}






//艹这个搞的我头疼
ListNode *reverseKGroup(ListNode *head, int k) {
    ListNode *headCheck = head;
    //
    for (int i = k; i > 0; i--) {
        if (headCheck == nullptr)
            return head;
        else
            headCheck = headCheck->next;
    }

    //翻转链表
    int count=0;
    ListNode *now = head;
    ListNode* firstPtr= nullptr;
    ListNode *nowNext = nullptr;

    //进行翻转
    while (count<k&&now!= nullptr)
    {
        //头插进行逆转
        nowNext=now->next;
        now->next=firstPtr;
        firstPtr=now;
        now=nowNext;
        count++;
    }

    //比如是2 3  三这边断开了
    //链接收尾1  2 3 | 4 5

    //用翻转后的尾结点链接 head 指向翻转后的链表尾部（因为head是头 反转后就是尾部）
    if (head!= nullptr)
        head->next=reverseKGroup(now,  k);


    return firstPtr;//返回头结点

}
}